class Solution {
public:
	//row行 col列  j[row][col]
	bool ifcomreg(int row, int col, vector<string>&temp, int n)
	{
		//找竖着的前半段  row行
		for (int i = 0; i < row; i++)
		{
			if (temp[i][col] == 'Q')
				return false;
		}
		//找上半段的45度角 从除了当前节点开始
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
		{
			if (temp[i][j] == 'Q')
				return false;
		}
		//找上半段的135度角 因为是135度，所以是从temp[row-1][col+1]开始,
		//即temp左上角第一个节点开始
		for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
		{
			if (temp[i][j] == 'Q')
				return false;
		}
		return true;
	}
	//row 行数 当前到第几行了
	void backtraing(int n, int row, vector<string>&temp)
	{
		if (row == n)
		{
			//结束了 丢进去 假如说女王在某一列没有任何位置放了,那么当col < n的时候,就结束了，也就进不去这里了
			result.push_back(temp);
			return;
		}
		for (int col = 0; col < n; col++)
		{
			if (ifcomreg(row, col, temp, n))//判断是否符合规定
			{
				//将那一行放上女王
				temp[row][col] = 'Q';
				backtraing(n, row + 1, temp);
				//撤销女王
				temp[row][col] = '.';
			}
		}
	}
	vector<vector<string>> result;
	vector<vector<string>> solveNQueens(int n) {
		//将整个数组都初始化成 .
		vector<string> temp(n, string(n,'.'));
		backtraing(n, 0, temp);
		return result;
	}
};